package leetcode.code0420;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

public class Solution2 implements IDebug {

	public int strongPasswordChecker(String password) {
		char[] cs = password.toCharArray();
		int len = cs.length;
		int upper = 0, lower = 0, digit = 0;
		char cur = 1;
		for (int i = 0; i < len; i++) {
			if ((cur = cs[i]) >= '0' && cur <= '9') {
				digit = 1;
			} else if (cur >= 'a' && cur <= 'z') {
				lower = 1;
			} else {
				upper = 1;
			}
		}
		// 需要create 或者 update cu个字符以达到种类相同
		int cu = 3 - upper - lower - digit;
		if (len < 6) {
			return Math.max(cu, 6 - len);
		}
		int d = Math.max(len - 20, 0);// 剩下要删除的数量
		int rest = len;// 剩下的字符数量
		char last = cs[0];
		int cnt = 1;// 连续的字符数量
		int u = 0;// 需要更新的次数，可以被删除省掉的更新次数
		int u2 = 0;// 省不掉的更新次数
		int delete = 0;// 用作删除动作的次数
//		PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->);
		for (int i = 1; i <= len; i++) {
			if (i < len && (cur = cs[i]) == last) {
				cnt++;
			} else {
				if (cnt >= 3) {
					// % 3== 0 还有删除余地的优先删除
					if (cnt % 3 == 0 && d > 0 && rest > 20) {
						delete++;
						d--;
						rest--;
						cnt--;
					}
					// 剩下的更新
					if (cnt % 3 == 2) {
						u2 += cnt / 3;// 删除两个不影响更新次数
					} else {// 余0 余1的情况一样
						u += cnt / 3;// 删除两个更新次数-1，剩余删除，优先删这个
					}
				}
				cnt = 1;
				last = cur;
			}
		}
		int d2 = 0;
		if (u > 0 && d > 1) {
			d2 = Math.max(u, d >> 1);
			u -= d2;
		}
		if (u2 > 0 && d > 3) {
			u2 -= Math.min(u2, d / 4);
		}
		return Math.max(u2 + u, cu) + d + delete;
	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

	@Override
	public void debug4() {
		HelpDebug.compare(23, this.strongPasswordChecker("FFFFFFFFFFFFFFF11111111111111111111AAA"));
		HelpDebug.compare(2, this.strongPasswordChecker("1234567890123456Baaaa"));
		HelpDebug.compare(13, this.strongPasswordChecker("aaaaaaaAAAAAA6666bbbbaaaaaaABBC"));
		HelpDebug.compare(3, this.strongPasswordChecker("aA345123451234512AAAAA"));
		HelpDebug.compare(5, this.strongPasswordChecker("1"));
		HelpDebug.compare(5, this.strongPasswordChecker("A"));
		HelpDebug.compare(5, this.strongPasswordChecker("a"));
		HelpDebug.compare(6, this.strongPasswordChecker(""));
		HelpDebug.compare(4, this.strongPasswordChecker("AAAAAABBBBBB123456789a"));
		HelpDebug.compare(10, this.strongPasswordChecker("hoAISJDBVWD09232UHJEPODKNLADU1"));
		HelpDebug.compare(3, this.strongPasswordChecker("..."));

		HelpDebug.compare(2, this.strongPasswordChecker("qqq123qqq"));
		HelpDebug.compare(2, this.strongPasswordChecker("QQQQQ"));
		HelpDebug.compare(2, this.strongPasswordChecker("aaaaaa"));
		HelpDebug.compare(2, this.strongPasswordChecker("1010101010aaaB10101010"));
		HelpDebug.compare(7, this.strongPasswordChecker("aaaaaaaaaaaaaaaaaaaaa"));
		HelpDebug.compare(3, this.strongPasswordChecker("abababababababababaaa"));
		HelpDebug.compare(0, this.strongPasswordChecker("1337C0d3"));
		HelpDebug.compare(6, this.strongPasswordChecker("ABABABABABABABABABABABAB"));
		HelpDebug.compare(5, this.strongPasswordChecker("a"));
		HelpDebug.compare(3, this.strongPasswordChecker("aA1"));

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

}
